Flash memory is a type of electrically erasable programmable read-only memory (EEPROM). Because flash memories are non-volatile and relatively dense, they are used to store files and other persistent objects in handheld computers, mobile phones, digital cameras, portable music players, and many other devices in which other storage solutions (e.g., magnetic disks) are inappropriate. Unfortunately, flash suffers from two limitations. First, bits can only be cleared by erasing a large block of memory. Second, each block can only sustain a limited number of erase operations, after which it can no longer reliably store data. Due to these limitations, complex data structures and algorithms are often required to effectively use flash memories. These algorithms and data structures are used to support efficient not-in-place updates of data, reduce the number of erase operations, and level the wear of the blocks in the device.
Flash memories do not support in-place updates or rewrites to physical memory pages unless the block containing the page is erased first. To overcome this deficiency, a hardware and/or software layer is often added to the flash subsystem. This layer, often referred to as a flash translation layer (FTL), along with the flash memory can mimic a secondary storage device by mapping logical sectors to physical memory pages. For many flash based devices, the FTL is implemented as a controller in hardware. The controller can include a processor or microcontroller along with small amounts of volatile memory (e.g., RAM). The controller can be responsible for translating a read/write request from the file system (e.g., a logical sector) into a read/write operation on a specific block of flash, and initiating “garbage collection” (GC) to erase dirty blocks and reclaim free blocks.
Flash devices can store the mapping of logical sectors to physical memory pages. The FTL can use this stored mapping to identify the physical location of logical sector. If a portion (e.g., a page) of the stored mapping is lost (e.g., data corrupted), the FTL may not be able to translate and perform read/write requests from the file system.